package io.zouyalong.algo.leetcode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * https://leetcode-cn.com/problems/first-missing-positive/
 */
public class FirstMissingPositive {
    public static void main(String[] args) {
        var nums = new int[]{0,2,2,4,0,1,0,1,3};
        var inst = new FirstMissingPositive();
        System.out.printf("%d\n", inst.solution3(nums));
    }
    /**
     * O(nlogn)
     * @param src
     * @return
     */
    public int solution1Force(int[] src) {
        Arrays.sort(src);
        int lastOccursNonNegative = 0;
        for (int each : src) {
            if (each >= 1) {
                if (each > lastOccursNonNegative+1) {
                    return lastOccursNonNegative+1;
                }
                lastOccursNonNegative = each;
            }
        }
        return lastOccursNonNegative+1;
    }

    public int solution2(int[] nums) {
        if (nums.length == 0) {
            return 1;
        }
        // 已出现的正整数中存在的空洞，比如当前的 missingPositive=2, 这时出现了3，则将3放到 remainGap 中，等到2出现时，再将3出队
        Queue<Integer> remainGap = new PriorityQueue<>();
        int missingPositive = 1;
        for (int each : nums) {
            if (each > 0) {
                if (each == missingPositive) {
                    missingPositive += 1;
                    for (;;) {
                        if (remainGap.isEmpty()) {
                            break;
                        }
                        if (missingPositive == remainGap.peek()) {
                            missingPositive+=1;
                            remainGap.poll();
                        } else if (missingPositive > remainGap.peek()) {
                            remainGap.poll();
                        } else {
                            break;
                        }
                    }
                } else if (each > missingPositive) {
                    remainGap.offer(each);
                } else {
                    // 重复出现, 忽略
                }
            }
        }
        return missingPositive;
    }
    public int solution3(int[] nums) {
        if (nums.length == 0) {
            return 1;
        }
        var nOccurs = new int[nums.length+1];
        for (int n : nums) {
            if (n >= 1 && n <= nums.length) {
                nOccurs[n] = 1;
            }
        }
        for (int i = 1; i <= nums.length; i++) {
            if (nOccurs[i] == 0) {
                return i;
            }
        }
        return nums.length+1;
    }
}
